package string;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Jisheng Huang
 * @version 20250607
 */
public class ClearStars_3170_2 {
    public static String clearStars(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        List<Integer>[] stacks = new ArrayList[26];
        Arrays.setAll(stacks, i -> new ArrayList<>());

        for (int i = 0; i < n; ++i) {
            if (arr[i] != '*') {
                stacks[arr[i] - 'a'].add(i);
                continue;
            }

            for (List<Integer> st : stacks) {
                if (!st.isEmpty()) {
                    arr[st.remove(st.size() - 1)] = '*';
                    break;
                }
            }
        }

        int idx = 0;

        for (int i = 0; i < n; ++i) {
            if (arr[i] != '*') {
                arr[idx++] = arr[i];
            }
        }

        return new String(arr, 0, idx);
    }

    public static void main(String[] args) {
        String s = "aaba*";
        System.out.println(clearStars(s));

        s = "abc";
        System.out.println(clearStars(s));
    }
}
